package alo.p12.work;

import org.junit.Test;

import java.util.Arrays;
import java.util.Random;

/**
 * @ClassName FindSecondMax
 * @Description 查找第二大元素
 * @Author Fanxc
 * @DATE 2021/3/14 10:55
 * @Version 1.0
 */
public class FindSecondMax {
    //不复制，空间O(n)
    int  findSecondMax(int[] a,int len){

        int aLen = 2*len;
        int[] ta=new int[len];
        int i;
        int secondLarge = -1;

        for(i=aLen-2;i>=2;i-=2){
            if(i>=len){
                ta[i/2] = Math.max(a[i-len],a[i+1-len]);
            }else if(i==len-1){
                ta[i/2] = Math.max(a[0],ta[i]);
            }else{
                ta[i/2] = Math.max(ta[i],ta[i+1]);
            }
        }

	    int max = ta[1];  //ta[1]即是保存的最大值
        System.out.println("最大值是："+max);

        //下面寻找第二大值，在直接输给最大值的的数中找
        for(i=1;2*i<aLen;){
            if(2*i<len-1){
                if(ta[2*i]==ta[i]){
                    if(secondLarge<ta[2*i+1])
                        secondLarge = ta[2*i+1];
                    i = 2*i;
                }else{
                    if(secondLarge<ta[2*i])
                        secondLarge = ta[2*i];
                    i = 2*i+1;
                }
            }else if(2*i==len-1){
                if(ta[2*i]==ta[i]){
                    if(secondLarge<a[0])
                        secondLarge = a[0];
                    i = 2*i;
                }else{
                    if(secondLarge<ta[2*i])
                        secondLarge = ta[2*i];
                    i = 2*i+1;
                }
            }else{
                if(a[2*i-len]==ta[i]){
                    if(secondLarge<a[2*i-len+1])
                        secondLarge = a[2*i-len+1];
                    i = 2*i;
                }else{
                    if(secondLarge<a[2*i-len])
                        secondLarge = a[2*i-len];
                    i = 2*i+1;
                }
            }
        }
	return secondLarge;
    }


    //锦标赛算法
    //复制，空间O(2n)
    public  int ChampionShip(int[] a) {
        int[] temp=new int[2*a.length];
        int secondMax=-0x3f3f3f3f;

        //将数组里面的数据填在临时数组中的temp[a.length-1]的后面
        if (temp.length - a.length >= 0)
            System.arraycopy(a, 0, temp, temp.length-a.length, a.length);

        //从后往前进行比较，将最大值以此填在temp[1]到temp[a.length-1]之间，则temp[1]是数组中的最大值
        for(int i=temp.length-2;i>=2;i-=2)
            temp[i/2]=Math.max(temp[i], temp[i+1]);

        //我们将从直接输给最大值的数中找到第二大的数
        for(int i=1;i<a.length;) {
            if(temp[i]==temp[2*i]) {
                if(secondMax<temp[2*i+1])
                    secondMax=temp[2*i+1];
                i=i*2;
            } else {
                if(secondMax<temp[2*i])
                    secondMax=temp[2*i];
                i=2*i+1;
            }
        }
        return secondMax;
    }

    @Test
    public void test() {
        // TODO Auto-generated method stub
        int[] a=new int[11];
        Random random=new Random();
        for(int i=0;i<a.length;i++)
            a[i]=random.nextInt(101);  //随机生成10个0到100的数字
        System.out.println("生成的结果是："+ Arrays.toString(a));
        int secondMax = ChampionShip(a);
        int second=findSecondMax(a,a.length);
        System.out.println("第二大的数是："+secondMax);
        System.out.println("第二大的数是："+second);
    }
}
